// 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

// 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/path-sum-iii
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;


// 思路正确，但是不会遍历节点，看了题解递归调用pathSum

// 执行用时：
// 20 ms
// , 在所有 C++ 提交中击败了
// 72.57%
// 的用户
// 内存消耗：
// 15.1 MB
// , 在所有 C++ 提交中击败了
// 94.47%
// 的用户

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };

class Solution {
public:
    int res=0;
    vector<TreeNode*> tree;
    int pathSum(TreeNode* root, int targetSum) {
        if(root ==NULL){
            return 0;
        }
        dfs(root,targetSum);
        pathSum(root->left,targetSum);
        pathSum(root->right,targetSum);
        return res;
    }
    void dfs(TreeNode* root,int targetSum){
        if(root ==NULL){
            return;
        }
        int temp = targetSum-root->val;
        if(temp==0){
            res++;
        }
        dfs(root->left,temp);
        dfs(root->right,temp);
    }
};